﻿#define _CRT_SECURE_NO_WARNINGS  1
#include"head.h"
//初始化
void HeapInit(Heap* hp)
{
	assert(hp);
	hp->a = NULL;
	hp->capacity = hp->size = 0;
}
// 堆的销毁
void HeapDestory(Heap* hp)
{
	assert(hp);
	free(hp->a);
	hp->a = NULL;
	hp->capacity = hp->size = 0;
}
void swap(HPDataType* p, HPDataType* q)
{
	int tem = *p;
	*p = *q;
	*q = tem;
}
void Adjustup(HPDataType* p, int child)
{
	assert(p);
	//寻找父亲  建小堆
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (p[parent] >p[child])
		{
			swap(&p[parent], &p[child]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
			break;
	}
}
// 堆的插入
void HeapPush(Heap* hp, HPDataType x)
{
	assert(hp);
	//检查容量
	if (hp->capacity == hp->size)
	{
		int newcapacity = hp->capacity == 0 ? 4 : hp->capacity * 2;
		HPDataType* newhead = (HPDataType*)realloc(hp->a, sizeof(HPDataType) * newcapacity);
		if (newhead == NULL)
		{
			perror("realloc fail");
			exit(-1);
		}
		hp->a = newhead;
		hp->capacity = newcapacity;
	}
	hp->a[hp->size] = x;
	hp->size++;
	Adjustup(hp->a, hp->size - 1);
}
void Adjustdown(HPDataType* p, int n, int parent)
{
	assert(p);
	int child = parent * 2 + 1;
	while (child<n)
	{
		if (child+1<n&&p[child + 1] > p[child])
		{
			child++;
		}
		if (p[child] > p[parent])
		{
			swap(&p[child], &p[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
			break;
	}
}
// 堆的删除
void HeapPop(Heap* hp)
{
	assert(hp);
	assert(hp->size > 0);
	swap(&hp->a[0], &hp->a[hp->size - 1]);
	hp->size--;
	Adjustdown(hp->a, hp->size, 0);
}
// 取堆顶的数据
HPDataType HeapTop(Heap* hp)
{
	assert(hp);
	return hp->a[0];
}
// 堆的数据个数
int HeapSize(Heap* hp)
{
	assert(hp);
	return hp->size;
}
// 堆的判空
int HeapEmpty(Heap* hp)
{
	assert(hp);
	return hp->size == 0;
}
//打印
void HeapPrint(Heap* hp)
{
	assert(hp);
	for (int i = 0; i < hp->size; i++)
	{
		printf("%d ", hp->a[i]);
	}
	printf("\n");
}
//void CreateNDate()
//{
//	// 造数据
//	int n = 10000;
//	srand(time(0));
//	const char* file = "data.txt";
//	FILE* fin = fopen(file, "w");
//	if (fin == NULL)
//	{
//		perror("fopen error");
//		return;
//	}
//
//	for (size_t i = 0; i < n; ++i)
//	{
//		int x = rand() % 1000000;
//		fprintf(fin, "%d\n", x);
//	}
//
//	fclose(fin);
//}
//void PrintTopK(const char* filename, int k)
//{
//	//CreateNDate();
//	//打开文件
//	FILE* point = fopen(filename, 'r');
//	if (point == NULL)
//	{
//		perror("filename fail");
//		return;
//	}
//	//开辟一个数组
//	int* heap = (int*)malloc(sizeof(int) * k);
//	if (heap == NULL)
//	{
//		perror("malloc fail");
//		return;
//	}
//	//读取前K个建堆
//	for (int i = 0; i < k; i++)
//	{
//		fscanf(point, "%d", &heap[i]);
//	}
//	//向下调整建小堆
//	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
//	{
//		Adjustdown(heap, k, i);
//	}
//	//遍历所有，小于 根 则插入
//	int j = 0;
//	while (fscanf(point, "%d", &j) != EOF)
//	{
//		if (heap[0] < j){
//			heap[0] = j;
//		}
//		Adjustdown(heap, k, 0);
//	}
//	for (int i = 0; i < k; i++)
//	{
//		printf("%d ", heap[i]);
//	}
//	printf("\n");
//
//	fclose(point);
//
//
//}